/**
 * @file DP.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-16
 *
 * @copyright Copyright (c) 2021
 *
 * 简单动规
 * 10.I.斐波那契数列
 * 10.II.青蛙跳台阶
 * 14.I.剪绳子
 * 14.II.剪绳子II -- 调大N，让dp失效
 * 19.正则表达式匹配 -- 难
 * 46.把数字翻译成字符串
 * 47.礼物最大值
 * 49.丑数
 * 60.n个骰子的点数
 * 63.股票的最大利润
 */

#include <cmath>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 10.I.
    int fib(int n)
    {
        int MOD = 1e9 + 7;
        if (n == 0 || n == 1) {
            return n;
        }
        int a = 0, b = 1;
        int c;
        for (int i = 2; i <= n; ++i) {
            c = a + b;
            c %= MOD;
            a = b;
            b = c;
        }
        return c;
    }
    // 10.II.
    int numWays(int n)
    {
        int MOD = 1e9 + 7;
        if (n == 0) {
            return 1;
        }
        if (n == 1 || n == 2) {
            return n;
        }
        int a = 1, b = 2;
        int c;
        for (int i = 3; i <= n; ++i) {
            c = a + b;
            c %= MOD;
            a = b;
            b = c;
        }
        return c;
    }
    // 14.I. 剪绳子
    int cuttingRope(int n)
    {
        // 整数拆分，每个数可拆成2个或大于等于3个
        // dp[i]=max(dp[i-j]*j, (i-j)*j) 枚举j
        vector<int> dp(n + 1, 0);
        dp[2] = 1;
        for (int i = 3; i <= n; ++i) {
            for (int j = 2; j < i; ++j) {
                dp[i] = max(max(dp[i - j] * j, (i - j) * j), dp[i]);
            }
        }
        return dp[n];
    }
    // 14.II 调大N范围，强行让你用数学方法呗~
    int cuttingRopeII(int n)
    {
        // 和I有啥区别？ n范围更大了 dp不行了
        if (n <= 3)
            return n - 1;
        if (n == 4)
            return 4;
        int MOD = 1e9 + 7;
        long res = 1;
        while (n > 4) {
            res *= 3;
            res %= MOD;
            n -= 3;
        }
        // 最后n的值只有可能是：2、3、4。而2、3、4能得到的最大乘积恰恰就是自身值
        // 因为2、3不需要再剪了（剪了反而变小）；4剪成2x2是最大的，2x2恰巧等于4
        return res * n % MOD;
    }
    // 19. 正则表达式p匹配字符串s
    // p只包含. * 字符
    bool isMatch(string s, string p)
    {
        // dp，对匹配方案枚举
        // dp[i][j] s的前i个字符 p的前j个字符是否能匹配
        // 当p[j]为字符或'.'时，只需判断s[i]==p[j]: dp[i][j]=dp[i-1][j-1]
        // 当p[j]=='*', 表示可以对p[j-1]匹配任意次数(包括0次)，不妨把'a*'当成整体

        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true; // 特殊情况：空串匹配空正则
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] != '*') { // p[j-1]为普通字符或'.'时
                    if (i > 0 && (s[i - 1] == p[j - 1] || p[j - 1] == '.')) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {          // p[j-1]为'*'时，可以对p[j-2]匹配任意次数(包括0次)，不妨把'a*'当成整体
                    if (j >= 2) { // 匹配0次，相当于j指针往前移2个位置
                        dp[i][j] = dp[i][j] | dp[i][j - 2];
                    }
                    // 匹配若干次，那就是j指针不动，i往前移
                    if (i > 0 && j >= 2 && (s[i - 1] == p[j - 2] || p[j - 2] == '.')) {
                        dp[i][j] = dp[i][j] | dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
    // 46.
    int translateNum(int num)
    {
        // dp[i] 表示以nums[i]为底时有多少种翻译方法
        // dp[i]=dp[i-1]          nums[i-1]和nums[i]组成数字在10到25之外
        // dp[i]=dp[i-1]+dp[i-2]
        string nums = std::to_string(num);
        int n = nums.size();
        vector<int> dp(n + 1, 0);
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            int twoBit = stoi(nums.substr(i - 2, 2));
            // cout << "两位数 " << twoBit << endl;
            if (twoBit >= 10 && twoBit <= 25) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        // print(dp);
        return dp[n];
    }
    // 47.
    int maxValue(vector<vector<int>> &grid)
    {
        int m = grid.size(), n = grid[0].size();
        cout << m << n << endl;
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; ++i) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < n; ++i) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
            }
        }
        // debug
        for (auto &d : dp) {
            print(d);
        }
        return dp[m - 1][n - 1];
    }
    // 49.
    int nthUglyNumber(int n)
    {
        // 法一：小顶堆：每次取出堆顶，把2x,3x,5x放入堆
        // 还要用set去重，复杂度O(NlogN)
        // 法二：动规：dp[i] 第i+1个丑数，dp[i]取2a,3b,5c最小值
        // a,b,c为dp索引
        int a = 0, b = 0, c = 0;
        int dp[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = min(min(n2, n3), n5);
            if (dp[i] == n2) {
                a++;
            }
            if (dp[i] == n3) {
                b++;
            }
            if (dp[i] == n5) {
                c++;
            }
        }
        return dp[n - 1];
    }
    // 60.
    vector<double> dicesProbability(int n)
    {
        // 投完第n枚骰子，点数j可由第n-1枚骰子j-1,j-2,..,j-6转换过来
        // dp[n][j] 第n个骰子，总点数为j的情况总数
        // dp[n][j] = Sigma i∈[1,6] (dp[n-1][j-i])
        vector<vector<int>> dp(n + 1, vector<int>(6 * n + 1, 0));
        vector<double> res;
        for (int i = 1; i <= 6; ++i) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; ++i) {         // 骰子个数
            for (int j = i; j <= 6 * i; ++j) { // 骰子j个时的总点数
                for (int k = 1; k <= 6 && k < j; ++k) {
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        int all = pow(6, n);
        for (int i = n; i <= 6 * n; ++i) {
            res.push_back((double)dp[n][i] / all);
        }
        return res;
    }
    // 63. 股票I, 只能买卖一次
    int maxProfit(vector<int> &prices)
    {
#ifdef DP63
        // dp[i][0] 第i天持有股票所得最多现金
        // dp[i][1] 第i天不持有股票所得最多现金
        // 最后返回dp[n-1][1]
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; ++i) {
            // 持有有2种情况：前一天就持有，当天买入(只能买卖一次)
            // 不持有也有2种情况：前一天就不持有，当天卖掉
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[n - 1][1];
#endif
        // 贪心，维护前i日最低价格和当前最大利润
        int cost = 1e5;
        int profit = 0;
        for (auto &price : prices) {
            cost = min(cost, price);            // 前i日最低价格
            profit = max(profit, price - cost); // 当前卖不卖？
        }
        return profit;
    }
};

void test10I()
{
    cout << Solution().fib(0) << endl;
    cout << Solution().fib(1) << endl;
    cout << Solution().fib(2) << endl;
    cout << Solution().fib(5) << endl;
    cout << Solution().fib(10) << endl;
    cout << Solution().fib(100) << endl;
}

void test10II()
{
    cout << Solution().numWays(0) << endl;
    cout << Solution().numWays(1) << endl;
    cout << Solution().numWays(2) << endl;
    cout << Solution().numWays(7) << endl;
    cout << Solution().numWays(10) << endl;
    cout << Solution().numWays(100) << endl;
}

void test14I()
{
    cout << Solution().cuttingRope(2) << endl;
    cout << Solution().cuttingRope(3) << endl;
    cout << Solution().cuttingRope(10) << endl;
    cout << Solution().cuttingRope(58) << endl;
}

void test14II()
{
    cout << Solution().cuttingRopeII(2) << endl;
    cout << Solution().cuttingRopeII(3) << endl;
    cout << Solution().cuttingRopeII(10) << endl;
    cout << Solution().cuttingRopeII(58) << endl;
    cout << Solution().cuttingRopeII(120) << endl;
    cout << Solution().cuttingRopeII(1000) << endl;
}

void test19()
{
    string s1 = "aa", p1 = "a";
    string s2 = "aa", p2 = "a*";
    string s3 = "ab", p3 = ".*";
    string s4 = "aab", p4 = "c*a*b";
    string s5 = "mississippi", p5 = "mis*is*p*.";
    cout << Solution().isMatch(s1, p1) << endl;
    cout << Solution().isMatch(s2, p2) << endl;
    cout << Solution().isMatch(s3, p3) << endl;
    cout << Solution().isMatch(s4, p4) << endl;
    cout << Solution().isMatch(s5, p5) << endl;
}

void test46()
{
    cout << Solution().translateNum(12258) << endl;
}

void test47()
{
    vector<vector<int>> grid1 = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
    vector<vector<int>> grid2 = {{1, 2, 5}, {3, 2, 1}};
    cout << Solution().maxValue(grid1) << endl;
    cout << Solution().maxValue(grid2) << endl;
}

void test49()
{
    cout << Solution().nthUglyNumber(8) << endl;
    cout << Solution().nthUglyNumber(9) << endl;
    cout << Solution().nthUglyNumber(10) << endl;
}

void test60()
{
    print(Solution().dicesProbability(1));
    print(Solution().dicesProbability(2));
}

int main()
{
    // test10I();
    // test10II();
    // test14I();
    // test14II();
    // test19();
    // test46();
    // test47();
    // test49();
    test60();
    return 0;
}